namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0222. 完全二叉树的节点个数")]
    public class No0222_CountNodes : AbsBaseTestItem
    {
        /*
        给出一个完全二叉树，求出该树的节点个数。
        说明：
            完全二叉树的定义如下：
                在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，
                并且最下面一层的节点都集中在该层最左边的若干位置。
                若最底层为第 h 层，则该层包含 1~ 2h 个节点。
        */

        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int x) { val = x; }
        }

        public override void OnTest()
        {
            TreeNode testNode = new TreeNode(1)
            {
                left = new TreeNode(2)
                {
                    left = new TreeNode(4),
                    right = new TreeNode(5),
                },
                right = new TreeNode(3)
                {
                    left = new TreeNode(6),
                },
            };

            Assert.TestExe(CountNodes, testNode, 6);
            Assert.TestExe(CountNodes_2, testNode, 6);
        }

        /// <summary>
        /// 最简单方法
        /// </summary>
        public int CountNodes(TreeNode root)
        {
            if (root == null) return 0;
            return 1 + CountNodes(root.left) + CountNodes(root.right);
        }

        /// <summary>
        /// LeetCode 官方方法一：二分查找 + 位运算
        /// </summary>
        public int CountNodes_2(TreeNode root)
        {
            bool exists(TreeNode root, int level, int k)
            {
                int bits = 1 << (level - 1);
                TreeNode node = root;
                while (node != null && bits > 0)
                {
                    if ((bits & k) == 0)
                    {
                        node = node.left;
                    }
                    else
                    {
                        node = node.right;
                    }
                    bits >>= 1;
                }
                return node != null;
            }

            if (root == null)
            {
                return 0;
            }
            int level = 0;
            TreeNode node = root;
            while (node.left != null)
            {
                level++;
                node = node.left;
            }
            int low = 1 << level, high = (1 << (level + 1)) - 1;
            while (low < high)
            {
                int mid = (high - low + 1) / 2 + low;
                if (exists(root, level, mid))
                {
                    low = mid;
                }
                else
                {
                    high = mid - 1;
                }
            }
            return low;
        }
    }
}
